package leetCode.hw.dp;

public class HJ24Solution implements HJ24 {

    @Override
    public int getMinOutNum(int[] queue) {
        int n = queue.length;
        int[] left = new int[n]; //存储每个数左边小于其的数的个数
        int[] right = new int[n];//存储每个数右边小于其的数的个数
        //初始化
        left[0] = 1;
        right[n - 1] = 1;
        //计算每个位置左侧开始的最长递增
        for (int i = 0; i < n; i++) {
            left[i] = 1;
            for (int j = 0; j < i; j++) {
                if (queue[i] > queue[j]) {
                    left[i] = Math.max(left[i],left[j] + 1);
                }
            }
        }
        //计算每个位置右侧开始的最长递减
        for (int i = n - 1; i >= 0; i--) {
            right[i] = 0;
            for (int j = n - 1; j > i; j--) {
                if (queue[i] > queue[j]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }
        // 记录每个位置的找到最大的满足要求的值
        int max = 0;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = left[i] + right[i];
            max = Math.max(result[i], max);
        }
        return n - max;
    }

    public static void main(String[] args) {
        int[] queue = {186,186,150,200,160,130,197,200};
        System.out.println(new HJ24Solution().getMinOutNum(queue));
    }

}
